1. Field of the Invention
The present invention relates to a Huffman encoder, a method for Huffman encoding and a recording medium having a program for a Huffman encoding process recorded thereon for encoding data which has been subjected to discrete cosine transformation into Huffman codes.
2. Description of the Prior Art
Image data includes a huge amount of information. It is therefore impractical to process image data as it is from the viewpoint of the memory capacity required therefor and communication speed. Techniques for compressing image data are therefore important.
One of international standards for image data compression is the JPEG (Joint Photographic Expert Group) standard. JPEG adopts the DCT (discrete cosine transformation) method which involves irreversible encoding and the reversible encoding method which involves DPCM (differential PCM) in a two-dimensional space. The compression of image data according to the DCT method will now be described.
FIG. 7 is a block diagram of a Huffman encoder which performs compression of image data according to the DCT method.
A DCT device 100 performs discrete cosine transformation (hereinafter referred to as xe2x80x9cDCTxe2x80x9d) on original image data input thereto and outputs DCT coefficients. During such DCT, as shown in FIG. 8, image data is divided into a plurality of pixel blocks each having 8xc3x978 pixels. As shown in FIG. 9, one 8xc3x978 pixel block includes 64 items of pixel data PXY (X, Y=0, . . . , 7). Two-dimensional DCT on an 8xc3x978 pixel block thus divided will provide 64 DCT coefficients SUV (U, V=0, . . . , 7).
The DCT coefficient S00, is referred to as xe2x80x9cDC coefficientxe2x80x9d, and the remaining 63 DCT coefficients are referred to as xe2x80x9cAC coefficientsxe2x80x9d. As shown in FIG. 9, the number of horizontal frequency components at high frequencies of a block which has been subjected to DCT is smallest at the left end of the block and is greatest at the right end, and the number of vertical frequency components at high frequencies is smallest at the top of the block and is greatest at the bottom.
A quantizer 110 shown in FIG. 7 quantizes DCT coefficients output by the DCT device 100 as expressed by the following equation using a quantization table consisting of 8xc3x978 quantization coefficients QUV (U, V=0, . . . , 7) to output quantized DCT coefficients xcex3UV (U, V=0, . . . , 7).
xe2x80x83xcex3UV=round (SUV/QUV)xe2x80x83xe2x80x83(1)
where xe2x80x9croundxe2x80x9d represents a process of rounding a number to the nearest integral number. Image quality and the amount of encoded information are controlled by such quantization. FIG. 10 shows examples of the DCT coefficients output by the quantizer 110. In FIG. 10, xe2x80x9cAxe2x80x9d, xe2x80x9cBxe2x80x9d, xe2x80x9cCxe2x80x9d, xe2x80x9cDxe2x80x9d, xe2x80x9cExe2x80x9d and xe2x80x9cFxe2x80x9d represent values other than xe2x80x9c0xe2x80x9d.
A Huffman encoding portion 120 in FIG. 7 encodes the DCT coefficients xcex3UV output by the quantizer 110 into Huffman codes to output encoded data. Referring to encoding of a DC coefficient, the difference between the DC coefficient of the current block and the DC coefficient of the preceding block is obtained, and the difference is encoded. In this case, differences between DC coefficients are grouped; and a group number SSSS is assigned to each difference; and a Huffman code is assigned to each group number SSSS.
Referring to encoding of AC coefficients, as shown in FIG. 11, the AC coefficients are first arranged on a one-dimensional basis as a result of a zigzag scan. The one-dimensionally arranged AC coefficients are encoded using run lengths NNNN representing the number of consecutive coefficients xe2x80x9c0xe2x80x9d (invalid coefficients) and the values of coefficients (valid coefficients) other than xe2x80x9c0xe2x80x9d. In this case, the valid coefficients are grouped, and a group number SSSS is assigned to each of the valid coefficients. When an AC coefficient is encoded, a Huffman code is assigned to a combination of the run length NNNN and the group number SSSS.
FIG. 12 shows an example of a table of Huffman codes for DC coefficients. For example, a Huffman code xe2x80x9c00xe2x80x9d having a code length of 2 is assigned to a DC coefficient difference whose group number SSSS is xe2x80x9c0xe2x80x9d; a Huffman code xe2x80x9c010xe2x80x9d having a code length of 3 is assigned to a DC coefficient difference whose group number SSSS is xe2x80x9c1xe2x80x9d; and a Huffman code xe2x80x9c011xe2x80x9d having a code length of 3 is assigned to a DC coefficient difference whose group number SSSS is xe2x80x9c2xe2x80x9d.
In the Huffman code table of FIG. 12, a group number SSSS only identifies the group to which a DC coefficient difference belongs. An additional bit is used to identify one of DC coefficients belonging to one group.
FIG. 13 shows an example of a table of Huffman codes for AC coefficients. For example, a Huffman code xe2x80x9c1010xe2x80x9d having a code length of 4 is assigned to an AC coefficient whose run length/group number combination NNNN/SSSS is xe2x80x9c0/0xe2x80x9d; a Huffman code xe2x80x9c00xe2x80x9d having a code length of 2 is assigned to an AC coefficient whose NNNN/SSSS is xe2x80x9c0/1xe2x80x9d; and a Huffman code xe2x80x9c01xe2x80x9d having a code length of 2 is assigned to an AC coefficient whose NNNN/SSSS is xe2x80x9c0/2xe2x80x9d.
In the Huffman code table of FIG. 13, a group number SSSS only identifies the group to which a valid coefficient belongs. An additional bit is used to identify one of valid coefficients belonging to one group.
FIG. 14 is a schematic view of an example of a Huffman encoding process in the Huffman encoder according to the related art shown in FIG. 7.
As shown in FIG. 14, DCT coefficients are quantized as expressed by Equation 1 to obtain quantized DCT coefficients xcex3UV. In the example shown in FIG. 14, a quantized DCT coefficient xcex300 of xe2x80x9c16xe2x80x9d is obtained from a DCT coefficient S00 of xe2x80x9c260xe2x80x9d and a quantization coefficient Q00 of xe2x80x9c16xe2x80x9d. Similarly, quantized DCT coefficients xcex301=4, xcex302=xe2x88x922, xcex310xe2x88x927, xcex311=3, xcex321=xe2x88x921 and xcex330=xe2x88x921 are obtained, and other quantized DCT coefficients xcex3UV are 0.
The quantized DCT coefficients xcex3UV are one-dimensionally arranged as a result of a zigzag scan to obtain run lengths representing the number of the coefficients xe2x80x9c0xe2x80x9d and valid coefficients. The first valid coefficient (DC coefficient) is xe2x80x9c16xe2x80x9d which is followed by run length/valid coefficient combinations of xe2x80x9c0/4xe2x80x9d, xe2x80x9c0/xe2x88x927xe2x80x9d, xe2x80x9c1/3xe2x80x9d, xe2x80x9c0/xe2x88x922xe2x80x9d, xe2x80x9c2/xe2x88x921xe2x80x9d and xe2x80x9c0/xe2x88x921xe2x80x9d, and the last run length is xe2x80x9c54xe2x80x9d.
In order to change the data compression rate of the above-described Huffman encoder according to the related art, the 8xc3x978 quantization coefficients QUV included in the quantization table must be changed. This makes a process for controlling the data compression rate complicated.
It is an object of the invention to provide a Huffman encoder, a method for Huffman encoding process, a program for a Huffman encoding process in which a data compression rate can be easily changed and a recording medium having the program for a Huffman encoding process recorded thereon.
A Huffman encoder for encoding a series of data into Huffman codes, according to an aspect of the invention comprises determination means for determining whether each item of a series of data is within a predetermined range and encoding means for performing encoding using combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data which are within the predetermined range, the valid coefficients being data out of the predetermined range.
In the Huffman encoder according to the invention, the determination means determines whether each item of a series of data is within a predetermined range. The encoding means treats data among the series of data which are within the predetermined range as invalid coefficients, treats data out of the predetermined range as valid coefficients and performs encoding using combinations of the number of consecutive invalid coefficients and valid coefficients.
In this case, the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range used by the determination means arbitrarily. This makes it possible to change the data compression rate easily.
In this case, the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range used by the determination means arbitrarily. This makes it possible to change the data compression rate easily.
The predetermined range can be arbitrarily set to a value larger than 0.
The Huffman encoder may further comprises quantization means for quantizing DCT coefficients using predetermined quantization coefficients and for supplying quantized DCT coefficients to the determination means as a series of data.
In this case, the DCT coefficients quantized by the quantization means using the quantization coefficients are supplied to the determination means as a series of data. Since the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range used by the determination means arbitrarily, the data compression rate can be easily changed without changing the quantization coefficients of the quantization means.
A Huffman encoder for encoding a series of data into Huffman codes, according to another aspect of the invention comprises a determination circuit for determining whether each item of a series of data is within a predetermined range and an encoding circuit for performing encoding using combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data which are within the predetermined range, the valid coefficients being data out of the predetermined range.
In the Huffman encoder according to the invention, the determination circuit determines whether each item of a series of data is within a predetermined range. The encoding circuit treats data among the series of data which are within the predetermined range as invalid coefficients, treats data out of the predetermined range as valid coefficients and performs encoding using combinations of the number of consecutive invalid coefficients and valid coefficients.
A method for Huffman encoding for encoding a series of data into Huffman codes, according to a further aspect of the invention comprises the steps of determining whether each item of a series of data is within a predetermined range and performing Huffman encoding using combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data within the predetermined range, the valid coefficients being data out of the predetermined range.
In the method for Huffman encoding according to the invention, it is determined whether each item of a series of data is within a predetermined range; data among the series of data which are within the predetermined range are treated as invalid coefficients; and data out of the predetermined range are treated as valid coefficients. Encoding is performed using combinations of the number of consecutive invalid coefficients and valid coefficients.
In this case, the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range arbitrarily. This makes it possible to change the data compression rate easily.
The series of data may be obtained by quantizing DCT coefficients using predetermined quantization coefficients.
In this case, the DCT coefficients quantized using the quantization coefficients are provided as a series of data. Since the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range used by the determination means arbitrarily, the data compression rate can be easily changed without changing the quantization coefficients of the quantization means.
In a recording medium having a processor-readable program for a Huffman encoding process recorded thereon, according to a further aspect of the invention, the program for a Huffman encoding process causes a processor to perform a process of determining whether each item of a series of data is within a predetermined range and a process of performing encoding utilizing combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data within the predetermined range, the valid coefficients being data out of the predetermined range.
According to the program for a Huffman encoding process according to the invention, it is determined whether each item of a series of data is within a predetermined range; data among the series of data which are within the predetermined range are treated as invalid coefficients; and data out of the predetermined range are treated as valid coefficients. Encoding is performed using combinations of the number of consecutive invalid coefficients and valid coefficients.
In this case, the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range arbitrarily. This makes it possible to change the data compression rate easily.
The program for a Huffman encoding process may further causes a processor to perform a process of obtaining a series of data by quantizing DCT coefficients using predetermined quantization coefficients.
In this case, the DCT coefficients quantized using the predetermined quantization coefficients are provided as a series of data. Since the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range arbitrarily, the data compression rate can be easily changed without changing the quantization coefficients.
A processor-readable program for a Huffman encoding process comprises the steps of causing the processor to perform a process of determining whether each item of a series of data is within a predetermined range and causing the processor to perform a process of performing encoding utilizing combinations of the number of consecutive invalid coefficients and valid coefficients, the invalid coefficients being data among the series of data within the predetermined range, the valid coefficients being data out of the predetermined range.
According to the program for a Huffman encoding process according to the invention, it is determined whether each item of a series of data is within a predetermined range; data among the series of data which are within the predetermined range are treated as invalid coefficients; and data out of the predetermined range are treated as valid coefficients. Encoding is performed using combinations of the number of consecutive invalid coefficients and valid coefficients.
In this case, the number of invalid coefficients can be arbitrarily adjusted by changing the predetermined range arbitrarily. This makes it possible to change the data compression rate easily.
The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.